package Lee_code;

/**
 * @author blh
 * @date 2024年08月12日 9:14
 */
public class Lee_437_811 {
    int res = 0;
    int tar;

    public int pathSum(TreeNode root, int targetSum) {
        tar = targetSum;
        // 传说中的二叉树的traceBack算法
        if (root == null) {
            return 0;
        }
        dfs(root, root.val);
        return res;
    }

    void dfs(TreeNode root, int curSum) {
        if (curSum == tar) {
            res++;
        }
        if (root.left != null) {
            dfs(root.left, curSum + root.left.val);
            dfs(root.left, root.left.val);
        }
        if (root.right != null) {
            dfs(root.right, curSum + root.right.val);
            dfs(root.right, root.right.val);
        }
    }
}
